package com.hy.three400;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:找到按位与最接近 K 的子数组
 * <p>
 * 给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位与运算 AND 的值与 k 的 绝对差
 * 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] AND nums[l + 1] ... AND nums[r])| 最小。
 * 请你返回 最小 的绝对差值。
 * 子数组是数组中连续的 非空 元素序列。
 * User:Mr.Du
 * Date:2024/6/2
 * Time:22:21
 */
public class MinimumDifference {
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            ans = Math.min(ans, Math.abs(x - k));
            for (int j = i - 1; j >= 0; j--) {
                // 如果 nums[j] 包含于 x，那么 j 及其左侧所有数（集合）都不会被更新
                // 也就是 A 包含于 B，那么 A ∩ B = A，A 不变
                if ((nums[j] & x) == nums[j]) {
                    break;
                }
                nums[j] &= x;  // 这里是 nums[j] 到 nums[i] 的子数组
                ans = Math.min(ans, Math.abs(nums[j] - k));
            }
        }
        return ans;
    }

}
